A* searching algorithm¶

A* is a heuristic searching algorithm that is used to find the shortest path between an initial and a final point. It is a handy algorithm that is often used for map traversal to find the shortest path to be taken. Here, we shall use this algorithm to find the shortest solution to the 8-puzzle problem

In [1]:
# we shall test our solution on these 3 puzzles

puzzle_1 = [
    [1, 2, 3],
    [7, 4, 5],
    [8, -1, 6]
]

puzzle_2 = [
    [1, 2, 3],
    [4, -1, 8],
    [7, 6, 5]
]

puzzle_3 = [
    [1, 8, 2],
    [-1, 4, 3],
    [7, 6, 5]
]

Function to implement slide and get coordinates of the empty space

In [2]:
def slide(arr: list, x: int, y: int, move: str):
        if(move == 'L'):
            arr[y][x-1], arr[y][x] = arr[y][x], arr[y][x-1]
        if(move == 'R'):
            arr[y][x+1], arr[y][x] = arr[y][x], arr[y][x+1]
        if(move == 'U'):
            arr[y-1][x], arr[y][x] = arr[y][x], arr[y-1][x]
        if(move == 'D'):
            arr[y+1][x], arr[y][x] = arr[y][x], arr[y+1][x]

def getXY(arr: list, e: int) -> tuple:
    n = len(arr)
    x = 0
    y = 0
    for i in range(n):
        for j in range(n):
            if arr[i][j] != e: continue
            x = j
            y = i
            break
    return (x, y)

Solution class¶

In [3]:
# we shall denote SPACE by -1

class Solver:
    def __init__(self, puzzle):
        self.SPACE = -1
        self.puzzle = [i[:] for i in puzzle]
        self.LENGTH = len(puzzle)
        self.solutions = []

    def getCost(self,arr) -> int:
        res = 0
        cost = 0

        for i in range(self.LENGTH):
            for j in range(self.LENGTH):
                if (i == self.LENGTH - 1) and (j == self.LENGTH - 1): res = self.SPACE
                else: res += 1
                cost += (arr[i][j] != res)
                
        return cost

    def getMinMoves(self):
        x, y = getXY(self.puzzle, self.SPACE)
        possible_moves = ['L', 'R', 'D', 'U']
        if x == 0: possible_moves.remove('L')
        if y == 0: possible_moves.remove('U')
        if x == self.LENGTH - 1: possible_moves.remove('R')
        if y == self.LENGTH - 1: possible_moves.remove('D')
        
        minCost = self.LENGTH ** 2
        move_cost = []

        for move in possible_moves:
            arr = [i[:] for i in self.puzzle]
            slide(arr, x, y, move)
            cost = self.getCost(arr)
            move_cost.append((move, cost))
            if cost < minCost: minCost = cost

        move_cost = [i[0] for i in filter(lambda v:v[1] == minCost, move_cost)]
        return (move_cost, x, y)

    def getSoln(self, move_list = []):

        if self.getCost(self.puzzle) == 0:
            self.solutions.append(move_list[:])
            return
        
        res = self.getMinMoves()
        for move in res[0]:
            
            # weed out consecutive moves
            if move_list != []:
                temp_str = move_list[-1] + move
                if (temp_str == 'LR' or 
                    temp_str == 'RL' or 
                    temp_str == 'UD' or 
                    temp_str == 'DU'): continue
            
            check_point = [i[:] for i in self.puzzle]
            slide(self.puzzle, res[1], res[2], move)
            self.getSoln(move_list + [move])
            self.puzzle = [i[:] for i in check_point]
            
    def solve(self):
        self.getSoln()
        self.solutions.sort(key = lambda x: len(x))

Driver code¶

In [4]:
if __name__ == "__main__":
    s1 = Solver(puzzle_1)
    s2 = Solver(puzzle_2)
    s3 = Solver(puzzle_3)
    s1.solve()
    s2.solve()
    s3.solve()
    print(s1.solutions)
    print(s2.solutions)
    print(s3.solutions)

[['L', 'U', 'R', 'R', 'D']]
[['R', 'D', 'L', 'U', 'R', 'D'], ['D', 'R', 'U', 'L', 'D', 'R']]
[['R', 'U', 'R', 'D', 'D', 'L', 'U', 'R', 'D']]

Visual representation¶

In [5]:
from IPython.display import HTML, display

s1.puzzle = [i[:] for i in puzzle_1]
s2.puzzle = [i[:] for i in puzzle_2]

def cell_to_table(arr, move):
    head = "<table>"
    
    s_arr = '&nbsp;'
    if move == 'L': s_arr = '&rarr;';
    if move == 'R': s_arr = '&larr;';
    if move == 'U': s_arr = '&darr;';
    if move == 'D': s_arr = '&uarr;';
    
    for i in arr:
        head += "<tr>"
        for j in i:
            if j == -1: head += f"<td class='ghost'>{s_arr}</td>"
            else: head += f"<td>{j}</td>"
        head += "</tr>"
    return head + "</table>"

def getHTML(sol: Solver, problem: int) -> str:
    table_html = ""
    sol_no = 1
    for solution in sol.solutions:
        table_html += f"<h2>Solution {sol_no}</h2><div class='flexbox'>"
        for move in solution:
            table_html += f"{cell_to_table(sol.puzzle, move)}<span class='arr'>&rarr;</span>"
            a, b = getXY(sol.puzzle, s1.SPACE)
            slide(sol.puzzle, a, b, move)
        table_html += cell_to_table(sol.puzzle, -1)
        table_html += "</div><br/>"
        sol.puzzle = [i[:] for i in puzzle_2]
        sol_no += 1
    return f"<h1>Problem: {problem}</h1><br/>{table_html}<hr/>"

display(HTML('''<style>
tr td{
    color: white;
    font-weight: bold;
    text-align: center;
    background-color: #1c7ed6;
}
.rendered_html tr,
.rendered_html th,
.rendered_html td{
     text-align: center;
     border: transparent;
     font-size: 2rem;
     padding: 20px;
     padding-bottom: 5px;
}
.rendered_html table{
    margin: 0px;
}
.ghost{
    border: none;
    background-color: transparent;
}
.flexbox{
    display: flex;
    padding: 0px;
    flex-direction: row;
    column-gap: 5px;
    justify-content: space-between;
}
.arr{
    font-size: 5rem;
    height: fit-content;
    margin-top: 50px;
}
</style>
''' + getHTML(s1, 1) + getHTML(s2, 2) + getHTML(s3, 3)))

Problem: 1


Solution 1

123
745
8→6
→
123
745
↓86
→
123
←45
786
→
123
4←5
786
→
123
45↑
786
→
123
456
78 

Problem: 2


Solution 1

123
4←8
765
→
123
48↑
765
→
123
485
76→
→
123
485
7↓6
→
123
4←5
786
→
123
45↑
786
→
123
456
78 

Solution 2

123
4↑8
765
→
123
468
7←5
→
123
468
75↓
→
123
46→
758
→
123
4↑6
758
→
123
456
7←8
→
123
456
78 

Problem: 3


Solution 1

182
←43
765
→
182
4↓3
765
→
1←2
483
765
→
12↑
483
765
→
123
48↑
765
→
123
485
76→
→
123
485
7↓6
→
123
4←5
786
→
123
45↑
786
→
123
456
78